Corso di Laurea in Informatica Linguaggio e Metodi della Matematica: Prova scritta del – 2002

COGNOME E NOME

MATRICOLA  CORSO  AULA

Firma

Esercizio 1. Si esprima in linguaggio naturale il significato della seguente formula e si trovi una sua forma normale prenessa

∀x∃y(x < y) → ¬∃y∀x(x ≤ y).

Esercizio 2. Usando le notazioni logiche, le costanti numeriche 0, 1, 2, …, e le operazioni di somma e prodotto, si esprima l’enunciato

“Ogni numero intero è pari o dispari”.

Esercizio 3. Dire se le seguenti inclusioni valgono per tutti gli insiemi A, B, C, D, motivando la risposta.

1. B ∩ D ⊆ (C ∩ B) ∪ (A ∩ D) ∪ (A ∩ C);

2. A ∪ C ∪ D ⊇ (B − A) ∩ C;

3. (B − D) − A ⊇ (B − A) − (C ∪ D).

Esercizio 4. Si considerino le stringhe di 7 simboli scelti tra le 21 lettere dell’alfabeto italiano (16 consonanti e 5 vocali).

1. Quante sono le stringhe che cominciano con una consonante e terminano con una vocale?

2. Quante sono le stringhe che hanno 4 consonanti (eventualmente ripetute) e 3 vocali (eventualmente ripetute)?

3. Quante sono le stringhe in cui almeno una lettera compare più di una volta?

Esercizio 5. Determinare per quali valori dell’intero n la congruenza 1547x ≡ 15n (mod 1751), e risolverla per n = 51.

Esercizio 6. Sia f_{n} la successione definita per ricorrenza ponendo f_{0} = 1, f_{1} = 2, e f_{n+1} = 3f_{n} − f_{n−1}.

1. Dimostrare che la successione è crescente.

COGNOME E NOME

MATRICOLA  CORSO  AULA

Firma

Esercizio 1. Si esprima in linguaggio naturale il significato della seguente formula e si trovi una sua forma normale prenessa

∃y∀x(x ≥ y) → ¬∀x∃y(x > y).

Esercizio 2. Usando le notazioni logiche, le costanti numeriche 0, 1, 2, 3, …, e le operazioni di somma e prodotto, si esprima l’enunciato

“Esiste un numero intero che non è nè pari nè multiplo di tre”.

Esercizio 3. Dire se le seguenti inclusioni valgono per tutti gli insiemi A, B, C, D, motivando la risposta.

1. B ∪ C ∪ D ⊇ (A − B) ∩ D;

2. A ∩ C ⊆ (A ∩ D) ∪ (B ∩ C) ∪ (B ∩ D);

3. (A − C) − B ⊇ (A − B) − (C ∪ D).

Esercizio 4. Si considerino le stringhe di 7 simboli scelti tra le 21 lettere dell’alfabeto italiano (16 consonanti e 5 vocali).

1. Quante sono le stringhe che cominciano con una vocale e che terminano con una vocale diversa?

2. Quante sono le stringhe che contengono una e una sola volta le tre vocali A, E, I?

3. Quante sono le stringhe che hanno almeno due lettere consecutive uguali?

Esercizio 5. Determinare per quali valori dell’intero n la congruenza 1729x ≡ 15n (mod 1957), e risolverla per n = 57.

Esercizio 6. Sia f_{n} la successione definita per ricorrenza ponendo f_{0} = 1, f_{1} = 5, e f_{n+1} = 5f_{n} − f_{n−1}.

1. Dimostrare che la successione è crescente.

COGNOME E NOME

MATRICOLA  CORSO  AULA

Firma

Esercizio 1. Si esprima in linguaggio naturale il significato della seguente formula e si trovi una sua forma normale prenessa

∃y∀x¬(x < y) → ∃y∀x(y ≤ x).

Esercizio 2. Usando le notazioni logiche, le costanti numeriche 0, 1, 2, …, e le operazioni di somma e prodotto, si esprima l’enunciato

“Se un numero è pari non è dispari”.

Esercizio 3. Dire se le seguenti inclusioni valgono per tutti gli insiemi A, B, C, D, motivando la risposta.

1. (B − C) − A ⊇ (B − A) − (C ∪ D).

2. A ∪ C ∪ D ⊇ (B − A) ∩ D;

3. B ∩ C ⊆ (B ∩ D) ∪ (A ∩ C) ∪ (A ∩ D);

Esercizio 4. Si considerino le stringhe di 7 simboli scelti tra le 26 lettere dell’alfabeto inglese (20 consonanti e 6 vocali).

1. Quante sono le stringhe che cominciano e finiscono con la stessa lettera?

2. Quante sono le stringhe che hanno 5 consonanti (eventualmente ripetute) e 2 vocali (eventualmente ripetute)?

3. Quante sono le stringhe in cui almeno una lettera compare più di una volta?

Esercizio 5. Determinare per quali valori dell’intero n la congruenza 1911x ≡ 15n (mod 2163), e risolverla per n = 63.

Esercizio 6. Sia f_{n} la successione definita per ricorrenza ponendo f_{0} = 1, f_{1} = 3, e f_{n+1} = 5f_{n} − 3f_{n−1}.

1. Dimostrare che la successione è crescente.

COGNOME E NOME

MATRICOLA  CORSO  AULA

Firma

Esercizio 1. Si esprima in linguaggio naturale il significato della seguente formula e si trovi una sua forma normale prenessa

¬∀y∃x(x < y) → ∃y∀x(y ≤ x).

Esercizio 2. Usando le notazioni logiche, le costanti numeriche 0, 1, 2, …, e le operazioni di somma e prodotto, si esprima l’enunciato

“Qualsiasi numero che divide 75 non è pari”.

Esercizio 3. Dire se le seguenti inclusioni valgono per tutti gli insiemi A, B, C, D, motivando la risposta.

1. A ∩ D ⊆ (C ∩ A) ∪ (B ∩ D) ∪ (B ∩ C);

2. B ∪ C ∪ D ⊇ (A − B) ∩ C;

3. (A − D) − B ⊇ (A − B) − (C ∪ D).

Esercizio 4. Si considerino le stringhe di 7 simboli scelti tra le 26 lettere dell’alfabeto inglese (20 consonanti e 6 vocali).

1. Quante sono le stringhe che cominciano con una consonante e che terminano con una consonante diversa?

2. Quante sono le stringhe che contengono esattamente una volta la lettera L ed esattamente due volte la lettera M?

3. Quante sono le stringhe che hanno almeno due lettere consecutive uguali?

Esercizio 5. Determinare per quali valori dell’intero n la congruenza 2093x ≡ 15n (mod 2369), e risolverla per n = 69.

Esercizio 6. Sia f_{n} la successione definita per ricorrenza ponendo f_{0} = 0, f_{1} = 3, e f_{n+1} = 7f_{n} − 3f_{n−1}.

1. Dimostrare che la successione è crescente.